{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "6fe01fae",
   "metadata": {},
   "source": [
    "## Problem A.Collatz conjecture sum\n",
    "The Collatz conjecture (https://en.wikipedia.org/wiki/Collatz_conjecture) is an unproven mathematical rule that says the following:\n",
    "Take any positive integer n. If n is even, divide it by 2 to get n / 2 (use integer division so that you don’t end up with floating point numbers). If n is odd, multiply it by 3 and add 1 to obtain 3n + 1. Repeat the process indefinitely, and eventually you will reach 1.\n",
    "Write a recursive function called collatz that takes in a single positive integer argument n and returns the sum of numbers in the collatz sequence from n to 1, inclusive.  For example, suppose your initial number was 5.  Then the collatz sequence would be the following:\n",
    "The initial number is 5.\n",
    "5 is odd, so the next number is 5*3 + 1 = 16\n",
    "16 is even, so the next number is 16//2 = 8\n",
    "8 is even, so the next number is 8//2 = 4\n",
    "4 is even, so the next number is 4//2 = 2\n",
    "2 is even, so the next number is 2//2 = 1\n",
    "We have reached 1, so the sequence is complete, and the function would return 36 (=5+16+8+4+2+1)\n",
    "Hints:\n",
    "You may assume that your function will only be called with positive integers.\n",
    "This function returns an int, so both your base case and your recursive case(s) need to return an int\n",
    "Constraints:\n",
    "The collatz function must be implemented using recursion.  Do not use any loop constructs (while or for).\n",
    "Examples:\n",
    ">>> collatz(5)\n",
    "36\n",
    ">>> collatz(1)\n",
    "1\n",
    ">>> collatz(123)\n",
    "6390"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 99,
   "id": "63d0bc29",
   "metadata": {},
   "outputs": [],
   "source": [
    "def collatz(n):\n",
    "    '''\n",
    "    Purpose: A recursive function called collatz that takes in a single positive \n",
    "    integer argument n and returns the sum of numbers in the collatz sequence from n to 1, inclusive. \n",
    "    n: A positive number\n",
    "    Return Value: An int\n",
    "    '''\n",
    "    \n",
    "    if n == 1:\n",
    "        return 1\n",
    "    if n % 2 == 1:\n",
    "        return collatz(3*n+1)+n\n",
    "    else:\n",
    "        return collatz(n//2)+n\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0d548950",
   "metadata": {},
   "outputs": [],
   "source": [
    "Problem B. (10 points) Positive reversibility\n",
    "Write a recursive function is_pos_reversible(alist) that takes a list of integers and tests whether the positive ints in that list could be read the same forward as backwards. The positions of 0s and negative values don’t matter.\n",
    "For example,is_pos_reversible([15, 2, 2, -1, 15, 0])\n",
    "should return True because if we ignore the negative values and the 0, the resulting list is\n",
    "[15, 2, 2, 15]\n",
    "which is the same forwards as it is backwards.\n",
    "Constraints:\n",
    "You may not use list methods (but slicing is allowed)\n",
    "You may not use loops of any sort\n",
    "Examples:\n",
    ">>> is_pos_reversible([4, 2, 3, 4])\n",
    "False\n",
    ">>> is_pos_reversible([15, 2, 2, -1, 15])\n",
    "True\n",
    ">>> is_pos_reversible([-12, 4, 23, 17, -12, 4, 17, 23, -1, 4, 0])\n",
    "True\n",
    ">>> is_pos_reversible([0])\n",
    "True\n",
    ">>> is_pos_reversible([])\n",
    "True\n",
    ">>> is_pos_reversible([5])\n",
    "True\n",
    ">>> is_pos_reversible([5, -1, -1, 4])\n",
    "False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 325,
   "id": "abba2d58",
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_pos_reversible(alist):\n",
    "    '''\n",
    "    Purpose: A function that takes a list of integers and tests whether the positive ints in that list could be read the same forward as backwards.\n",
    "    The positions of 0s and negative values don’t matter.\n",
    "    alist: A list\n",
    "    Return Value: Boolean value\n",
    "    '''\n",
    "    if len(alist)==0 or len(alist) == 1:\n",
    "        return True\n",
    "    if alist[0] <= 0:\n",
    "        return is_pos_reversible(alist[1:])\n",
    "    elif alist[-1] <= 0:\n",
    "        return is_pos_reversible(alist[:-1])\n",
    "    else:\n",
    "        return bool((alist[0]==alist[-1])*is_pos_reversible(alist[1:-1]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "56606202",
   "metadata": {},
   "outputs": [],
   "source": [
    "Problem C. (10 points) All subsets\n",
    "Write a recursive function all_subsets that takes as a parameter a list of items and returns a list containing all subsets (i.e. all lists containing some of the items from the original list.) \n",
    "We will treat these subsets as mathematical sets, therefore order does not matter. For this function, you may need to use a loop construct as well as a recursive call.\n",
    "Hint: There are a few ways to go about this, so I encourage you to find your own strategy before reading this.  But if you're stuck:\n",
    "Suppose you have a list of three elements: ['a', 'b', 'c'].  If you have the answer for a two element list (['a', 'b']):\n",
    "[[], ['a'], ['b'], ['a', 'b']]\n",
    "Then you can expand this into an answer for a three element list by making two copies of the above list: one where you add 'c' to each inner list, and one where you don’t:\n",
    "[[], ['a'], ['b'], ['a', 'b']]\n",
    "[['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c']]\n",
    "and then concatenating the two together:\n",
    "[[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c']]\n",
    "Constraints:\n",
    "The all_subsets function must be implemented using recursion.  You can (but do not have to) use a loop construct in addition to recursion, but a solution that does not use recursion in a meaningful way towards solving the problem will receive very little credit.\n",
    "You are not allowed to import any modules.\n",
    "Examples (order does not matter in the inner lists or the outer list):\n",
    ">>> all_subsets([100])\n",
    "[[], [100]]\n",
    ">>> all_subsets([])\n",
    "[[]]\n",
    ">>> all_subsets(['a', 'b', 'c'])\n",
    "[[], ['c'], ['b'], ['b', 'c'], ['a'], ['a', 'c'], ['a', 'b'], ['a', 'b', 'c']]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 396,
   "id": "cbab6273",
   "metadata": {},
   "outputs": [],
   "source": [
    "def all_subsets(alist):\n",
    "    '''\n",
    "    Purpose: A function that takes as a parameter a list of items and returns a list containing all subsets\n",
    "    alist: A list\n",
    "    Return Value: All the subsets of alist\n",
    "    '''\n",
    "    if alist == []:\n",
    "        return [[]]\n",
    "    return all_subsets(alist[1:]) + [[alist[0]]+i for i in all_subsets(alist[1:])]"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
